#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define rep(i, s, t) for (int i = s; i <= t; ++i)
#define per(i, s, t) for (int i = t; i >= s; --i)

const int N = 1e5 + 5;
const int M = N * 25;

int n, q;
vector<int> adj[N];
int rt[N], ls[M], rs[M], tt;
ll val[M][3];
ll f[N];

inline void add(int& o1, int o2, int p, int a, int b, int c, int l, int r) {
	o1 = ++tt;
	ls[o1] = ls[o2];
	rs[o1] = rs[o2];
	val[o1][0] = val[o2][0] + a;
	val[o1][1] = val[o2][1] + b;
	val[o1][2] = val[o2][2] + c;
	if(l == r) return;
	int mid = l + r >> 1;
	if(p <= mid) add(ls[o1], ls[o2], p, a, b, c, l, mid);
	else add(rs[o1], rs[o2], p, a, b, c, mid + 1, r);
}

inline ll query(int o, int ql, int qr, int a, int b, int c, int l, int r) {
	if(!o) return 0;
	if(ql <= l && r <= qr) {
		// cerr << "[" << l << ", " << r << "] = " << "(" << val[o][0] << ", " << val[o][1] << ", " << val[o][2] << ")\n";
		return a * val[o][0] + b * val[o][1] + c * val[o][2];
	}
	int mid = l + r >> 1;
	ll res = 0;
	if(ql <= mid) res += query(ls[o], ql, qr, a, b, c, l, mid);
	if(mid < qr) res += query(rs[o], ql, qr, a, b, c, mid + 1, r);
	return res;
}

inline ll query(int l, int r, int ql, int qr, int a, int b, int c) {
	if(l > r || ql > qr) return 0;
	return query(rt[r], ql, qr, a, b, c, 1, n) - query(rt[l-1], ql, qr, a, b, c, 1, n);
}

inline ll solve(int l, int r) {
	// cerr << "cost(" << l << ", " << r << ") = ";
	// cerr << "\n";
	ll res = 0;
	res += query(l, r, l, r, r-l, 1, -1);
	// cerr << res << "\n";
	res += query(1, l, r, n, 1, 0, 0);
	// cerr << res << "\n";
	int mid = l + r >> 1;
	res += query(l+1, mid, r+1, n, -l, 1, 0);
	res += query(mid+1, r, r+1, n, r+1, -1, 0);
	mid = l + r + 1 >> 1;
	res += query(1, l-1, l, mid-1, -l+1, 0, 1);
	res += query(1, l-1, mid, r-1, r, 0, -1);
	// cerr << res << "\n";
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cout << fixed << setprecision(15); 
	cerr << fixed << setprecision(15);
	
	freopen("block.in", "r", stdin);
	freopen("block.out", "w", stdout);
	
	cin >> n >> q; --n;
	rep(i, 1, q) {
		int l, r; cin >> l >> r; --r;
		adj[l].pb(r);
	}
	rep(i, 1, n) {
		rt[i] = rt[i-1];
		for(int j : adj[i]) {
		// cerr << "[" << i << ", " << j << "]\n";
			add(rt[i], rt[i], j, 1, i, j, 1, n);
		}
	}
	deque<tuple<int, int, int>> dq;
	dq.emplace_back(0, 1, n);
	// rep(i, 1, n) rep(j, i, n) solve(i, j);
	memset(f, 0x3f, sizeof f);
	f[0] = 0;
	// rep(i, 1, n) {
		// rep(j, 0, i-1) f[i] = min(f[i], f[j] + solve(j+1, i));
	// }
	// rep(i, 1, n) cerr << f[i] << " \n"[i == n];
	rep(i, 1, n) {
		int j = get<0>(dq.front());
		f[i] = f[j] + solve(j+1, i);
		// cerr << j << " -> " << i << " " << f[i] << " " << f[j] << "\n";
		while(!dq.empty()) {
			auto [j, l, r] = dq.front();
			if(r < i+1) dq.pop_front();
			else {
				dq.pop_front();
				dq.emplace_front(j, max(l, i+1), r);
				break;
			}
		}
		while(!dq.empty()) {
			auto [j, l, r] = dq.back();
			if(f[i] + solve(i+1, l) < f[j] + solve(j+1, l)) {
				dq.pop_back();
			} else {
				break;
			}
		}
		if(dq.empty()) dq.emplace_back(i, i+1, n);
		else {
			auto [j, l, r] = dq.back();
			int L = l, R = r, p = r + 1;
			while(L <= R) {
				int mid = L + R >> 1;
				if(f[i] + solve(i+1, mid) < f[j] + solve(j+1, mid)) p = mid, R = mid - 1;
				else L = mid + 1;
			}
			if(p != n+1) {
				dq.pop_back();
				dq.emplace_back(j, l, p-1);
				dq.emplace_back(i, p, n);
			}
		}
	}
	cout << f[n] << "\n";
	
	return 0;
}
